函数式语言SML简介

2018-05-01

函数式语言SML简介

摘要

从函数式语言家族的起源来看，其问世以来的数十年间，始终是作为一类小众的语言。大多数情况下，只有实验室对其进行一些理论上的研究。但是，随着编程语言的不断发展，我们看到越来越多的主流语言，将函数式特性或者函数式思想纳入到了自己的体系之中。

通过对于函数式语言特性的分析，我们可以了解到其独特的优点。正式由于其严格的类型检查和良好的封装，使得程序员能加不容易写出错误的程序。同时，得益于其数学思想，程序员可以很方便的写出更加优雅且利于并行的程序。这正是函数式特性在现代编程语言如C++、Java、Python不断得到加强的原因。

在下一篇文章中，我们将通过一个简单的数据结构(AVL平衡二叉树)，对比了函数式语言和命令式语言的区别和联系。并且，通过一些大样例的实验，分析函数式和命令式语言在运行速度方面的特点。

结果，函数式语言的表现不容乐观，与C语言的差距非常巨大。在代码书写上可能SML体验更佳。但是效率的问题，导致了其只能用于教学和科研。

关键词：函数式特点 AVL数据结构命令式对比 $\lambda$表达式

函数式语言特点

封装

计算机的构造十分的复杂，如果学习过计算机组成原理、操作系统或者系统结构必然知道，不论是CPU的流水执行、Cache的缓存命中、分页分段调度还是进程间通信等等，都是极为复杂的。如果不是专业去编写OS或者对于性能要求极为苛刻的处理程序，我们几乎不可能也不必要去关心这些过于底层的问题。

正如芯片对电路的封装、操作系统对硬件的封装一样，编程语言也存在了大量的封装。高级的编程语言如C/C++，将程序变得易读易写。但是，这些语言在抽象的程度上，仍然没有摆脱硬件的控制，将一条条的语句翻译成了命令让计算机去执行。由于全局变量、共享环境等等因素，程序很容易出现意想不到的问题，写出的程序也很难并行的调用。

但是函数式语言如ML的抽象却要高出很多。过程式的语言是面向命令的，而函数式语言，则是面向表达式的。函数式编程是一种编程模型，它将计算机运算看作是数学中函数的计算，并且避免了状态以及变量的概念。在函数式编程中所有的状态都是不可变的。一个val x = x + 1的程序段，仅仅是将x声明为x + 1这个值的别名。并没有修改原先的内容。同样，如果另外的一个函数里面使用了这个别名，函数的执行结果也不会随着x的变化而变化，值已经和函数绑定在了一起。

同时，在ML语言中，我们也不必去关心内存分配的问题。和Java语言类似，程序员不需要考虑内存泄漏或者野指针之类的问题，ML提供了GC(垃圾回收)的机制，编写难度上要减少很多。

###函数“一等公民”

程序完全由函数构成，函数操控者数据结构。使用这个语言的人，完全不用关心计算机底层的内容。通过一个个数学表达式，就可以实现自己的目的。每次调用一个函数，对于同样的参数，获得的结果一定是相同的。没有“副作用”的产生。命令式编程天生的缺陷使并行编程模型变得非常复杂，都使程序员不堪重负，函数式编程语言的优势体现出来。函数式编程没有可变的变量，数据只读不写，因此，并发的问题迎刃而解。而且，相对于命令式编程而言，函数式编程大幅简化了并行计算的编写难度，不易出错且易于维护。这就是引用透明性。

因为函数作为”一等公民“，我们可以很简单的将函数作为一个参数或者返回值使用。在C语言当中，我们可以通过传递函数指针的方式，来实现函数参数的调用。但是，指针毕竟只是指针，我们所传递的只是函数的执行地址，仍然摆脱不了底层的计算机结构。在C++11和Java8以后，我们可用通过$\lambda$表达式的方法，实现函数的传递。但是，从编译的角度上讲，这两种OOP的语言，仅仅是生成了一个匿名的类(Class)，使用的时候，传递了一个对象进去执行。

但是，在函数式语言ML中，我们可以很方便的使用函数的特性，实现一个柯里函数(currying)。比如如下的例子：

- fun mul x y z = x * y * z;
val mul = fn : int -> int -> int -> int
- val f = mul 2 3;
val f = fn : int -> int
- f 10;
val it = 60 : int

可以看到，我们首先定义了一个mul函数，但是此函数经过了柯里化，如果使用命令式的思维来理解，这个函数接受一个int型的参数，返回一个接受int参数返回接受int参数返回int的函数的函数的函数。那么，使用这个函数，我们可以创造出新的函数，比如，val f = mul 2 3里面，f作为一个函数类型的值，它接受到一个int参数，并且返回此参数乘以6的结果。

此外，利用这一特性，我们可以很容易的利用如flodr、map这样的高阶函数，实现批量的操作。算子是一种操作于另一个或者另几个函数之上的函数。对于map算子，当应用到函数$f$上时，返回另外的一个函数。实现如下的转化：
$$
[x_1, x_2, \ldots, x_n] \Rightarrow [f(x_1), f(x_2), \ldots, f(x_n)]
$$
对于另一个高阶函数foldr，应用于$f$和一个参数$e$时，实现了$f(x_1, f(x_2, \ldots, f(x_n, e)\ldots))$的效果，镜像对称的foldl，实现了$f(\ldots f(f(e, x_1), x_2)\ldots x_n)$。

虽然现代的编程语言普遍支持了map、foreach的操作，但是仍然没有函数式语言自然。

多态类型检测

ML在运行之前，编译器会检测所有模块的接口是否相容，以及数据是否一致的被使用。ML使用了模式匹配(pattern-matching)来分析参数。

ML使用多态类型检测(polymorphic type checking)，大大减少了错误的产生的概率。对于C/C++之类的语言，隐式的类型转化虽然可以减少很多的代码量，但是也经常会导致严重的极难以察觉的bug。

在C++中，参数可能发生隐式的转化或者其他一些由于编译器实现导致的问题。比如在C++编译器可能会将NULL定义为((void)0)或者int类型的0。由于C++禁止(void )类型的隐式转化，对于如下的语句：

1	double dp = NULL; // 对于NULL = (void )0 的情况，此句不能通过编译

如果定义为(void *)0，会出现无法隐式转换的问题。

但是即使使用简单的int型的0，在使用函数重载的时候，仍然会出现冲突，比如如下的情况：

void f(char *);
void f(int);
int main () {
	f(NULL);
}

这里产生了二义性的冲突，一般情况下，程序员认为传递一个NULL指针，应该去调用char 类型，但是这里却违反直觉的出现了编译错误。编译器无法判断NULL应该调用int还是char 。幸运的是，在C++11标准中，nullptr的引入解决了这个问题。并且，可以通过对于函数加入explicit禁止隐式的类型转化。但是，仍然没有给出一个足够的保证，使得程序员不会出错。

同时，多态类型的引入，既保证了强类型语言的安全性，同时也十分的灵活方便。大多数的类型都是自动推导过来的。ML的多态性是基于类型模式的，这个类似于类型的模版。